{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## 62 & 63\n",
    "### 62. Unique Paths\n",
    "A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).\n",
    "\n",
    "The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).\n",
    "\n",
    "How many possible unique paths are there?\n",
    "\n",
    "<div align=\"center\">\n",
    "    <img src=\"./images/robot_maze.png\" width=\"50%\">\n",
    "    <Figure>Above is a 7 x 3 grid. How many possible unique paths are there?</Figure>\n",
    "</div>\n",
    "\n",
    "    Example 1:\n",
    "        Input: m = 3, n = 2\n",
    "        Output: 3\n",
    "        Explanation:\n",
    "        From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:\n",
    "        1. Right -> Right -> Down\n",
    "        2. Right -> Down -> Right\n",
    "        3. Down -> Right -> Right\n",
    "\n",
    "    Example 2:\n",
    "        Input: m = 7, n = 3\n",
    "        Output: 28\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "from math import factorial\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        # def iterator(m, n):\n",
    "        #     if m == 1 or n == 1:\n",
    "        #         return 1\n",
    "        #     else:\n",
    "        #         return iterator(m - 1, n) + iterator(m, n - 1)\n",
    "        # return iterator(m, n)\n",
    "\n",
    "        # dynamic programming\n",
    "        return int(factorial(m + n - 2) / factorial(m - 1) / factorial(n - 1))\n",
    "\n",
    "\n",
    "S = Solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "m, n = 3, 2\n",
    "print(S.uniquePaths(m, n))\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "28\n"
     ]
    }
   ],
   "source": [
    "m, n = 7, 3\n",
    "print(S.uniquePaths(m, n))\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 63. Unique Paths II\n",
    "A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).\n",
    "\n",
    "The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).\n",
    "\n",
    "Now consider if some obstacles are added to the grids. How many unique paths would there be?\n",
    "\n",
    "<div align=\"center\">\n",
    "    <img src=\"./images/robot_maze.png\" width=\"50%\">\n",
    "    <Figure>An obstacle and empty space is marked as 1 and 0 respectively in the grid.</Figure>\n",
    "</div>\n",
    "\n",
    "**Note**: m and n will be at most 100.\n",
    "\n",
    "    Example 1:\n",
    "        Input:\n",
    "        [\n",
    "          [0,0,0],\n",
    "          [0,1,0],\n",
    "          [0,0,0]\n",
    "        ]\n",
    "        Output: 2\n",
    "        Explanation:\n",
    "        There is one obstacle in the middle of the 3x3 grid above.\n",
    "        There are two ways to reach the bottom-right corner:\n",
    "        1. Right -> Right -> Down -> Down\n",
    "        2. Down -> Down -> Right -> Right"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if obstacleGrid[i][j] == 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if i == 0 and j == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    elif i == 0:\n",
    "                        dp[i][j] = dp[i][j - 1]\n",
    "                    elif j == 0:\n",
    "                        dp[i][j] = dp[i - 1][j]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "S = Solution()"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "obstacleGrid = \\\n",
    "    [\n",
    "      [0,0,0],\n",
    "      [0,1,0],\n",
    "      [0,0,0]\n",
    "    ]\n",
    "\n",
    "print(S.uniquePathsWithObstacles(obstacleGrid))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "obstacleGrid = [[1]]\n",
    "print(S.uniquePathsWithObstacles(obstacleGrid))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "obstacleGrid = [[1, 0]]\n",
    "print(S.uniquePathsWithObstacles(obstacleGrid))\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}